package io.github.handyang.algorithms.digraph;

import io.github.handyang.algorithms.Bag;

/**
 * 邻接数组
 */
public class ArrayDigraph implements Digraph {
    private final Bag[] adj;

    private int E;

    public ArrayDigraph(int V) {
        adj = new Bag[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i] = new Bag();
        }
    }

    @Override
    public int V() {
        return adj.length;
    }

    @Override
    public int E() {
        return E;
    }

    @Override
    public void addEdge(int v, int w) {
        adj[v].add(w);
        E++;
    }

    @Override
    public Iterable<Integer> adj(int v) {
        return adj[v];
    }

    @Override
    public Digraph reverse() {
        ArrayDigraph reverse = new ArrayDigraph(V());

        for (int i = 0; i < adj.length; i++) {
            Bag bag = adj[i];

            for (Object point : bag) {
                reverse.addEdge((Integer) point, i);
            }
        }

        return reverse;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder("\n");
        for (int i = 0; i < adj.length; i++) {
            builder.append(i).append(":").append(adj[i].toString()).append("\n");
        }

        return builder.toString();
    }
}
